|
In graph theory, a well-covered graph is an undirected graph in which every minimal vertex cover has the same size as every other minimal vertex cover. Well-covered graphs were defined and first studied by . ==Definitions== A vertex cover in a graph is a set of vertices that touches every edge in the graph. A vertex cover is minimal, or irredundant, if removing any vertex from it would destroy the covering property. It is minimum if there is no other vertex cover with fewer vertices. A well-covered graph is one in which every minimal cover is also minimum; in the original paper defining well-covered graphs, writes that this is "obviously equivalent" to the property that every two minimal covers have the same number of vertices as each other. An independent set in a graph is a set of vertices no two of which are adjacent to each other. If is a vertex cover in a graph , the complement of must be an independent set, and vice versa. is a minimal vertex cover if and only if its complement is a maximal independent set, and is a minimum vertex cover if and only if its complement is a maximum independent set. Therefore, a well-covered graph is, equivalently, a graph in which every maximal independent set has the same size, or a graph in which every maximal independent set is maximum. In the original paper defining well-covered graphs, these definitions were restricted to apply only to connected graphs,〔.〕 although they are meaningful for disconnected graphs as well. Some later authors have replaced the connectivity requirement with the weaker requirement that a well-covered graph must not have any isolated vertices.〔.〕 For both connected well-covered graphs and well-covered graphs without isolated vertices, there can be no ''essential vertices'', vertices which belong to every minimum vertex cover.〔 Additionally, every well-covered graph is a critical graph for vertex covering in the sense that, for every vertex , deleting from the graph produces a graph with a smaller minimum vertex cover.〔 The independence complex of a graph is the simplicial complex having a simplex for each independent set in . A simplicial complex is said to be pure if all its maximal simplices have the same cardinality, so a well-covered graph is equivalently a graph with a pure independence complex.〔For examples of papers using this terminology, see and .〕 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Well-covered graph」の詳細全文を読む スポンサード リンク
|